package com.leetcode;

/**
 * 149. 直线上最多的点数
 *
 * @author fy
 * @date 2022/4/8 19:30
 */
public class Solution149 {

    public int maxPoints1(int[][] points) {
        if (points == null) {
            return 0;
        }
        if (points.length < 3) {
            return points.length;
        }

        int maxCount = 2;
        for (int i = 0; i < points.length - 2; i++) {
            int[] p = points[i];
            int x1 = p[0];
            int y1 = p[1];
            for (int j = i + 1; j < points.length - 1; j++) {
                int[] q = points[j];
                int x2 = q[0];
                int y2 = q[1];
                boolean flag = false;
                double a = 0;
                double b = 0;
                if (x1 - x2 == 0) {
                    flag = true;
                    b = -x1;
                } else {
                    a = (double) (y1 - y2) / (x1 - x2);
                    b = y1 - x1 * a;
                }

                int areaCount = 2;
                for (int k = j + 1; k < points.length; k++) {
                    int[] n = points[k];
                    if (flag) {
                        if (n[0] + b == 0) {
                            areaCount++;
                        }
                    } else {
                        if (a * n[0] + b == n[1]) {
                            areaCount++;
                        }
                    }
                }

                if (areaCount > maxCount) {
                    maxCount = areaCount;
                }
            }
        }
        return maxCount;
    }

    public int maxPoints(int[][] points) {
        if (points == null) {
            return 0;
        }
        if (points.length < 3) {
            return points.length;
        }

        int maxCount = 2;
        for (int i = 0; i < points.length; i++) {
            int[] p = points[i];
            int x1 = p[0];
            int y1 = p[1];
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int[] q = points[j];
                int x2 = q[0];
                int y2 = q[1];
                boolean flag = false;
                double a = 0;
                double b = 0;
                if (x1 - x2 == 0) {
                    flag = true;
                    b = -x1;
                } else {
                    a = (double) (y1 - y2) / (x1 - x2);
                    b = y1 - x1 * a;
                }

                int areaCount = 2;
                for (int k = 0; k < points.length; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    int[] n = points[k];
                    if (flag) {
                        if (n[0] + b == 0) {
                            areaCount++;
                        }
                    } else {
                        // 浮点数存在误差, 需要怎么解决??
                        if (Math.abs(a * n[0] + b - n[1]) < 0.0001) {
                            areaCount++;
                        }
                    }
                }

                if (areaCount > maxCount) {
                    maxCount = areaCount;
                }
            }
        }
        return maxCount;
    }

    public static void main(String[] args) {
        int[][] points = new int[][]
                {
                        {54, 153},
                        {1, 3},
                        {0, -72},
                        {-3, 3},
                        {12, -22},
                        {-60, -322},
                        {0, -5},
                        {-5, 1},
                        {5, 5},
                        {36, 78},
                        {3, -4},
                        {5, 0},
                        {0, 4},
                        {-30, -197},
                        {-5, 0},
                        {60, 178},
                        {0, 0},
                        {30, 53},
                        {24, 28},
                        {4, 5},
                        {2, -2},
                        {-18, -147},
                        {-24, -172},
                        {-36, -222},
                        {-42, -247},
                        {2, 3},
                        {-12, -122},
                        {-54, -297},
                        {6, -47},
                        {-5, 3},
                        {-48, -272},
                        {-4, -2},
                        {3, -2},
                        {0, 2},
                        {48, 128},
                        {4, 3},
                        {2, 4}
                };

        int res = new Solution149().maxPoints(points);
        System.out.println(res);
    }

}
